CD Actual 1

home *** CD-ROM | disk | FTP | other *** search

/ CD Actual 1 / PC Actual CD 01.iso / share / dos / demos / planets / doc.lzh / PLANET.TXT < prev

Wrap

Text File | 1994-05-01 | 45.1 KB | 1,075 lines

The Definitive Guide to Bouncing Planets (a document with a modest title) Simon Hern 22 Harrington Drive Bedford MK41 8DB England This document describes how to create a computer animation of a rotating planet using simple texture-mapping techniques. It should make an interesting programming project for someone with a basic knowledge of assembly language and computer graphics. August, 1992 Revised December, 1992 Revised April, 1994 1. Introduction 1.1. Planets, Past and Present In the spring of 1990 a computer animation of a rotating planet lived out a brief, anonymous but happy existence. Years have passed. Now here's the sequel. The greatest improvement of this program over the hacked-together- in-Basic original is the neatness and completeness of its design. More interesting improvements are: * Faster animation techniques. * Choice of planet sizes and axes of rotation. * Generation of semi-convincing planet surfaces. * Illumination effects. The makers of the original 'Star Trek' would've died to use this animation as a special effect. That's how good it is. 1.2. Disclaimers and Apologies There are a few things I ought to mention before going on. Firstly, I am by no stretch of the imagination an expert in computer graphics, or for that matter computer programming of any description. Nearly all of what follows I figured out for myself during boring physics lessons (something I've always felt quite proud of). If there are any books that describe how to do this sort of thing, I've never seen them (though I would certainly like to). Secondly, a work of stunning originality this isn't. When I started this project I had never seen or heard of anything like it. But that was probably more by chance than anything else since I've now had reports of people writing spinning planet animations (along very similar lines to what I'm describing here) as far back as the mid-eighties. Finally, I must apologize for the naming of some of the concepts described here (Gush, Complexion, Riff, etc). They are not technical terms, merely the inventions of a warped mind (I was reading a lot of Clive Barker books at the time). That's enough of that. Now on with the show. 1.3. Overview of the Program The planet program divides up into three basic segments which I will cover (in long-winded detail) in turn. The first part of the program creates a large array of data called the Gush which is required for the rapid animation of the planet. See Section 2. The second part of the program generates a random surface for the planet and gives it colour. The resulting data array is called the Complexion. See Section 3. The third part of the program uses these two data arrays to animate the planet in real time. For each frame of animation the entire planet is redrawn, rotated as required. See Section 5. Sections 4 and 6 contain details on how the animation can be implemented in practice. 1.4. Planet Shapes and Sizes The following constant values appear in various places throughout the program. They control certain aspects of the planet's appearance. RADIUS This (integer) value is the radius in pixels of the planet as it appears on the screen. DIST This is the apparent distance of the observer from the planet. It is measured in pixels from the planet's centre and would usually take a value in the order of several times the width of the screen. It must have a value greater than that of RADIUS. (The effect this value has is, to be honest, pretty minimal.) rho This value (an integer) is the resolution of the planet's surface. It is the number of points of latitude (north to south) and half the number of points of longitude (around the equator) used when giving coordinates to the landscape. phi This is the angle through which the axis of rotation of the planet is tilted backwards from the vertical (as seen by the observer). theta This is the angle through which the axis of rotation of the planet is turned clockwise (as seen by the observer). phi and theta do not need to be in any particular units since it is their sines and cosines that are required and the units conversion can take place when these are calculated. These constants will be discussed in more detail as they are used. 2. Writing the Gush: Data for Spinning a Planet 2.1. From Screen to Surface A lot of calculations need to be performed before drawing a planet. To speed up the animation procedure, the results of most of these calculations are worked out in advance and stored in a data array which I call the Gush. The Gush consists of data for transforming points of the planet as seen on the screen to points on the mercator map of the planet's surface. Two stages are required to create the Gush. The first stage considers the Gush as a two-dimensional grid (the Square Gush), with each point corresponding to a pixel on the screen, and performs the lengthy floating-point calculations. In the second stage the data in the Gush is rearranged to make it more readily accessable to the animation routines. This second stage Gush is called the Line Gush. 2.2. Constants and the Gush All of the constants described in Section 1.4 are referred to in the Gush calculations. It is worth noting that the values of DIST, phi, theta and (possibly) RADIUS are needed only when creating the Gush and will probably not appear anywhere else in the program. As a result, Gushes created using different values for these constants can be used interchangeably. 2.3. The Square Gush The Square Gush is an array of size 2*RADIUS by 2*RADIUS and is referenced by variables xs and ys, both of which take values from 0 to 2*RADIUS-1. Each entry in the array holds two values: xm and ym, both non-negative integers of size depending on the choice of rho. The array will be described using the notation gush[ys][xs].xm_val and gush[ys][xs].ym_val to mean the values of xm and ym at the (xs,ys) position in the array. The points of the Square Gush correspond directly to the pixels of the planet's image on the screen; the empty space around the planet is represented by null values in the array. The values of xm and ym for a point (xs,ys) are calculated in the following way. First, define a new constant, g, as g = DIST * RADIUS / sqrt( DIST*DIST + RADIUS*RADIUS ) [sqrt() meaning 'square root'] Next, to make the calculations faster, work out the sines and cosines of phi and theta, calling them sph, sth, cph and cth. For each point (xs,ys) evaluate the following temporary values: xg = xs - RADIUS + 0.5 yg = ys - RADIUS + 0.5 j = sqrt( xg*xg + yg*yg ) If j is greater than RADIUS then (xs,ys) is not a point in the planet's image and should be ignored; set xm = ym = -1 (or some other null value). Otherwise, h = sqrt( DIST*DIST * ( g*g - j*j ) + g*g * j*j ) k = ( DIST*DIST - h ) / ( DIST*DIST + j*j ) xp = k * xg yp = k * yg zp = sqrt( g*g - xp*xp - yp*yp ) (The vector (xp,yp,zp), called P, can be used to calculate illumination effects. See Section 6.2.) xt = xp*cth - yp*sth*cph + zp*sth*sph yt = xp*sth + yp*cth*cph - zp*cth*sph zt = yp*sph + zp*cph w = sqrt( g*g - yt*yt ) alpha = acos( yt / g ) beta = acos( - xt / w ) [acos() meaning 'inverse cosine'] All of these calculations use floating-point arithmetic. xm and ym, on the other hand, are integers, and when converting from floating-point to integer values in the next set of calculations the 'integer part' of the number (the largest integer not greater than that number) should be taken. xm = (int) beta * rho / pi ym = (int) alpha * rho / pi [pi is (predictably enough) the constant 3.14159265(etc). All the trigonometric calculations here operate in radians.] if xm = rho then let xm = rho - 1 if ym = rho then let ym = rho - 1 if zt < 0 then let xm = 2*rho - 1 - xm xm takes values from 0 to 2*rho-1 and ym takes values from 0 to rho-1. These are the coordinates of a point on the mercator map of the planet's surface. The values of xm and ym can now be stored in the Gush array. gush[ys][xs].xm_val = xm gush[ys][xs].ym_val = ym 2.4. The Line Gush The Line Gush is all of the important data from the Square Gush rearranged in such a way as to make the final animation as fast as possible (this being where the name 'Gush' comes in). The Line Gush takes the form of a one-dimensional array, a string of values in the order they are used to draw the planet. The actual format of the Line Gush is determined by the procedure used to display the planet. Here is an example Line Gush format. For more details see Sections 4 and 5. The first entry in the Line Gush is the number of horizontal lines needed to draw the planet, i.e., the planet's height in pixels. It is equal to 2*RADIUS. Since the planet is circular, these horizontal lines will be of different lengths. The Square Gush treats all the lines as being of the same length and fills in the gaps with 'null' entries. These nulls are missed out when putting together the Line Gush. Now, for each horizontal line of the planet (corresponding to each value taken by ys), the following values are stored in the Line Gush: (1) The relative screen position of the start of the line. Since the lines are all of different lengths, the Gush must provide information on how to arrange them to give a circular shape. This information will probably take the form of an amount to be added to the screen address of the last point plotted on the previous line to give the address of the first point to plot on this new line. (2) A function of the length of the line; this value determines the number of points to plot. (For speed of animation, it may be other than simply the number of points on the line.) (3) For each point on the line, that point's xm and ym values (possibly combined into a single value). It takes a considerable amount of time to create a full (Line) Gush so it is advisable to save the completed data to disk rather than to create new data each time. There is no simple formula for the size of the Line Gush, but in the above example it will be smaller than the Square Gush which consists of 2*4*RADIUS*RADIUS bytes (or words, depending on how xm and ym are stored). An alternative approach is to create a Compiled Gush, an executable mixture of data and machine code which allows for very fast animation, but which takes up a large amount of memory. 3. Third Day Song 3.1. Making Planets This part of the program creates a random, vaguely realistic- looking planet surface which is something like fractally generated. (In my brief search around the library I couldn't find any (comprehensible) information about generating realistic spherical planet surfaces.) The method used is as follows. The planet's surface (a sphere) is cut around a random equator into two hemispheres. One of the hemispheres is selected and the altitudes of all points on it increased or decreased relative to the other hemisphere. This is repeated many times with the relative changes in altitude gradually reducing in significance. This process acts on an array of altitude values called the Skin, which describes in a two dimensional mercator map the spherical planet surface. When the Skin is complete it is transformed into an array of colour values called the Complexion. It is this which is used in the animation. 3.2. The Skin The Skin is a two-dimensional array of size rho by 2*rho (this being the definition of the value rho), and each entry in it represents the altitude of a point on the surface of the planet. The Skin will be referred to by skin[y][x] where y is the colatitude of a point on the surface and takes values from 0 to rho-1, and x is the longitude of a point on the surface and takes values from 0 to 2*rho-1. Note that the skin wraps around in the x sense (so x=2*rho is equivalent to x=0), but not in the y sense; y=0 marks the north pole, y=rho-1 marks the south pole. The elements in this array could be floating-point numbers, but, to speed up calculations, it is probably best to use integers. All of the altitude values are initially set to zero, or some other appropriate base value. 3.3. The Riffs To generate the planet's surface, the Skin must be treated as if it is spherical when it is, in fact, flat. This is achieved with the help of a set of data arrays, called the Riffs, which describe the shapes of the possible fractures that can be made in the surface. The Riffs are unchanging; the random planet surfaces (for fixed rho) are all created using the same set of Riffs. There are rho/2 Riffs, numbered from 0 to rho/2-1, each consisting of rho/2 (again 0 to rho/2-1) integer values between 0 and rho/2 inclusive. Let the Riffs be represented by riff[A][t] where A is the Riff number and t is the position within that Riff. The Riffs are generated in the following way with A and t both taking values 0 to rho/2-1: omega = ( A + 0.5 ) * pi / rho sigma = ( t + 0.5 ) * pi / rho gamma = atan( tan(omega) * cos(sigma) ) riff[A][t] = rho/2 - round( gamma * rho / pi ) [round() means 'to the nearest integer'. atan() means 'inverse tangent'.] It can take a little time to create all the Riffs, so it is not a bad idea to save them to disk for future use. 3.4. The Song This section describes the actual routine that generates the planet's surface. It is fairly complicated. For this part of the program the Skin (with all entries initially set to zero), the Riffs, and the constant rho are required. A couple of new constants also need to be defined. FULL_BLAST This value determines the size of the fractures made in the surface; it is the actual size of the first fracture made. POWER This constant controls the style of formation of the surface. A value of 1 results in mostly straight coastlines whilst a higher value gives more jagged shapes. Try a value of 3, 4 or 5. The number of 'strikes' used to make the surface (and hence the time taken) is equal to FULL_BLAST to the power of POWER. Something in the order of several thousand strikes I find are needed to generate a convincing surface. The procedure that follows is written in an vague approximation of the C language. FULL_BLAST = 20.0 POWER = 3.0 int skin[rho][2*rho]; /* Using integer altitude values */ int riff[rho/2][rho/2]; /* Riff data already generated */ int strike; /* Number of fractures to make */ int displac = 0; /* Move everything upwards; rebalance later */ int blast; /* Depth of next fracture */ int rf_num; /* Riff to use on this fracture */ int r1; /* Preliminary random choice of riff */ int half; /* Random choice of which half of surface to hit */ int dirn; /* Random choice of whether to blast up or down */ int x_start; /* Position around equator to start at */ float r2, dis; /* Weight riff probabilities */ int x, y; /* Every program needs some x and y coordinates */ int x1, x2, x3, x4; /* A few spare x coordinates */ /* 'strike' is initially FULL_BLAST to the power of POWER */ /* We repeat until strike (decremented by one each time) is zero */ for ( strike = pow( FULL_BLAST, POWER ) ; strike > 0 ; strike-- ) { /* pow(A,B) means A to the power of B (A^B or A**B) */ /* Watch out for conversions between 'int' and 'float' here */ blast = FULL_BLAST / pow( strike, 1.0/POWER ); /* Choose random values for next fracture */ r1 = random(rho/2); /* int from 0 to rho/2-1 (inclusive) */ x_start = random(2*rho); /* 0 to 2*rho-1 (inclusive) */ half = random(2); /* 0 or 1 */ dirn = random(2); /* 0 or 1 */ r2 = ((float)rand())/(float)RAND_MAX; /* between 0 and 1 */ /* Balance choice of riffs evenly over the surface */ /* (Avoids most fractures being along the equator) */ dis = sin( pi * (r1+0.5) / rho ); /* All in floating-point */ if ( r2 <= dis*dis ) rf_num = r1; else rf_num = rho/2 - 1 - r1; /* We only displace in the northern half of the planet */ /* then make up for it at the end using 'displac' */ if ( dirn == 0 ) blast = -blast; if ( half == 0 ) displac = displac - blast; /* This loop would be best converted to assembly language */ /* The loop goes from x equal to 0 to x equal to rho/2-1 */ /* Note: A%B means the remainder of A divided by B (A mod B) */ /* A+=B means A=A+B */ for ( x = 0 ; x < rho/2 ; x++ ) { x1 = ( x_start + x ) % (2*rho); x2 = ( x_start + 2*rho-1 - x ) % (2*rho); for ( y = 0 ; y < riff[rf_num][x] ; y++ ) { /* If riff[rf_num][x] is zero this loop is not executed */ skin[y][x1] += blast; skin[y][x2] += blast; } x3 = ( x_start + rho + x ) % (2*rho); x4 = ( x_start + rho-1 - x ) % (2*rho); for ( y = 0 ; y < rho-1 - riff[rf_num][x] ; y++ ) { /* If riff[rf_num][x] is rho-1 this loop is not executed */ skin[y][x3] += blast; skin[y][x4] += blast; } } } /* Finally, shift all the altitudes to rebalance the zero level */ /* (This is not strictly necessary since altitudes are relative) */ for( y = 0 ; y < rho ; y++ ) for( x = 0 ; x < 2*rho ; x++ ) skin[y][x]+=displac; This routine assumes that the Skin is made up of integer values and so uses mostly integer variables. The advantages of using ints rather than floats are that they use less memory, they operate faster, and they allow the program to be more easily converted into assembly language. Bear in mind that integer variables can 'overflow' if they are required to store very large numbers. If the program begins to produce unexpected results, this could be the cause. 3.5. The Complexion The Complexion is an array of the same size and shape as the Skin and is referred to by xion[y][x]. Each entry in the Complexion is a colour value and the array as a whole forms a coloured-in map of the planet's surface. The Complexion is derived from the Skin by assigning colours based on the altitude at each point. A simple way to do this is as follows. Choose a set of K colours such that colour 1 represents the lowest altitude and colour K represents the highest altitude. Look at the Skin to find the maximum and minimum altitude values and divide up the range of altitudes into K equal-sized groups, each corresponding to a colour. Then, if the maximum and minimum altitudes are the values max and min, xion[y][x] = int{ ( skin[y][x] - min ) * K / (max-min+1) } + 1 For a very simple planet design, colour any point with an altitude of (max+min)/2 or less sea-blue, and any other point grass-green. 4. Notes on Implementation 4.1. Attachment to Hardware The details of writing this program depend greatly on the hardware being used: the CPU instruction set, the available memory, the graphics specifications and the computer's speed, among other things. In this section I'll sketch out how I envisage this program being implemented to make the most of the hardware available. 4.2. Choice of Screen Mode The way in which the screen memory of the computer is organised determines to a large extent the structure of the animation routine. The simplest way to write to the screen would be to use a function of the type plot(x_pos, y_pos, colour), but this would give painfully slow animation. It is usually much better to write directly to screen memory. The nicest screen mode for this sort of animation would have each pixel controlled by one byte of screen memory (suggesting a mode with 256 colours) and would have consecutive pixels along a horizontal line corresponding to consecutive bytes in memory, with the horizontal lines arranged in order top to bottom. With other kinds of screen arrangement animation routines become a little more tricky to put together. Some screen modes use pixels which aren't exact squares, and this results in planets that are elliptical instead of circular. To compensate for this the (xs,ys) coordinates used in the Square Gush have to be rescaled (the result being, in effect, a Rectangular Gush). The choice of screen resolution is a balancing of two factors: for planets of a fixed size, a low-resolution display gives a less detailed image whilst a high-resolution display means slower animation. A resolution of about 300 pixels by 200 pixels with a planet radius of 50 pixels (which is to say RADIUS=50) is a reasonable place to start. 4.3. Gush Structure The amount of memory needed for the Gush depends on a lot of factors; anything from two to ten bytes may be needed for each point to be plotted, the number of which will be around PI*RADUIS*RADIUS. A straightforward Line Gush for a planet with RADIUS=50 and rho=128 may take up around 20k. A Compiled Gush for the same planet may take up closer to 60k. The value DIST has only a very slight effect on the appearance of the planet. I usually give it a value somewhere in the thousands. It can alternatively be omitted altogether: change the Gush calculations so that g=RADIUS and k=1. This is equivalent to making DIST infinitely large (and has the advantage of speeding up the Gush calculations.) As default values for phi and theta, try 45 and 30 degrees respectively. 4.4. Complexion Structure The resolution of the planet's surface, rho, should be given a value in compromise of two factors: if rho is not large enough the planet's surface will be too blocky, but as rho becomes larger more memory is required for the Complexion and more time is needed to generate a planet surface. Also, very large values of rho give no obvious improvement to the appearance of the planet. In addition, the value of rho determines the number of different frames seen when the planet is animated; the number of positions of rotation the planet can be viewed in is equal to 2*rho. In general, rho can be given any value, but a value of 128 may give certain advantages. Since the array xion[y][x] uses values of x between 0 and 2*rho-1 and values of y between 0 and rho-1, rho=128 means that both x and y values are byte-sized. Also, the offset into the xion array is 2*rho*y+x which becomes 256*y+x, so x and y are now the low order and high order bytes of a CPU-friendly 16-bit word. Each point in the Complexion is a colour value; if no more than 256 colours are used, then each entry in the array will take up one byte. The total amount of memory used will then be 2*rho*rho bytes. 5. Magrathea in Scattered Jumps: Plotting a Planet 5.1. Animation Routines And so, at last, we arrive at the heart of the program: the animation routine. What I'm going to do in this section is describe a progression of methods for displaying planets, starting with simple routines to help explain the process and then moving on to more effective methods. Since the speed of the display routine is critical it will almost certainly need to be written in assembly language. With this in mind, the descriptions of the routines are in a fairly low-level pseudo-code. Four bits of data are needed by the routines when displaying a planet: xion The routine must have access to some Complexion data; the name xion will be used to mean, depending upon the routine, either the entire array xion[y][x] or the address in memory of (i.e., a pointer to) the first byte in the array. gush The routine needs Gush data of some description. Like xion, gush will refer to either an array or a memory address as the routine requires. scr This value determines where on the screen the planet is displayed. It could be either the x and y coordinates of a point on the screen (referred to as scr.x and scr.y), or the address of a point in screen memory. The point in question will be the top-left 'corner' of the planet. rot This is the state of rotation of the planet, the degree to which it appears rotated about its axis when drawn. It is a value between 0 and 2*rho-1 with wrap-around meaning that rot=2*rho is equivalent to rot=0. 5.2. Using the Square Gush This is the simplest of the display methods; it uses the Square Gush as input, treating it as an array, and plots points to the screen using a plot function. This method could be implemented in a high-level language to test how well the program works before going to the trouble of writing a faster assembly language routine. In addition to the parameters which are passed to the routine (see 5.1), five local variables are used here: ys and xs are the coordinates of a point in the Gush and on the screen; col is the colour of the current point; xm and ym are values taken from the Gush data which refer to a point in the Complexion. Remember that the Square Gush includes a number of 'null' entries for which both xm_val and ym_val are taken here to be equal to -1. ys = 0 L1: xs = 0 L2: xm = gush[ys][xs].xm_val ym = gush[ys][xs].ym_val if ( xm = -1 ) and ( ym = -1 ) jump to L3 xm = ( xm + rot ) % (2*rho) col = xion[ym][xm] plot( (scr.x + xs), (scr.y + ys), col ) L3: xs += 1 if ( xs != 2*RADIUS ) jump to L2 ys += 1 if ( ys != 2*RADIUS ) jump to L1 It should be obvious roughly what this routine does. For each point in an area of the screen, xm and ym values are taken from the corresponding point in the Square Gush. If the point is valid (i.e., part of the planet) then a colour value is derived from the Complexion and the point is plotted. The value rot is added to xm, the result being trimmed so that it remains between 0 and 2*rho-1. In this way, the planet's surface is effectively made to rotate around the planet. (This is the only time that rot is used in the program.) (Incidentally, 'A != B' means 'A not equal to B' and 'A % B' means 'remainder of A divided by B'.) 5.3. Using the Line Gush Because the Line Gush does not include the 'null' entries of the Square Gush, a routine using it can run faster. The Line Gush is a sequence of values in memory which are accessed in order. The notation x=[gush++] will be used to mean 'load the next Gush value into x' - the variable/register gush holds the address of the next value to be used; this value is loaded into x and gush is incremented by an appropriate amount. The format of the Line Gush is defined by the structure of the routine. In this example, the first value is the total number of lines to draw and is followed by the appropriate data for each line consisting of: (1) An amount to add to or subtract from scr.x, the x-coordinate of the next point to be plotted, so that this line is drawn to fit the circular shape of the planet. (2) The number of points to be plotted on this line. (3) For each point on this line, a value for xm followed by a value for ym. The local variables used in this routine are the same as those used in Section 5.2 except that xs and ys are renamed xcount and ycount to reflect their slightly different application. ycount = [gush++] L1: scr.x += [gush++] xcount = [gush++] L2: xm = [gush++] ym = [gush++] xm = ( xm + rot ) % (2*rho) col = xion[ym][xm] plot( scr.x, scr.y, col ) scr.x += 1 xcount -= 1 if ( xcount != 0 ) jump to L2 scr.y += 1 ycount -= 1 if ( ycount != 0 ) jump to L1 Note that the value of RADIUS is no longer needed here - all the required data is stored in the Gush. 5.4. Screen Memory Addresses The most obvious way of increasing the speed of the previous routine is to avoid using the plot function and to instead write directly to the screen memory. Section 4.2 lists the assumptions I am making about the layout of the screen memory. The variable/register named scr will now hold the memory address of the next point of the screen to be altered. The notation [scr]=x will be used to mean that the byte or word at screen memory address scr is to be loaded with the value x. Apart from scr, the only other difference between this routine and the last one is in the Line Gush: the value which before was added to scr.x is now added to scr. This new value is the difference between the address of the last point on the previous line of the planet and the address of the first point on the new line of the planet. ycount = [gush++] L1: scr += [gush++] xcount = [gush++] L2: xm = [gush++] ym = [gush++] xm = ( xm + rot ) % (2*rho) col = xion[ym][xm] [scr] = col scr += 1 xcount -= 1 if ( xcount != 0 ) jump to L2 ycount -= 1 if ( ycount != 0 ) jump to L1 5.5. Games with Xion All of the routines so far have treated xion as an array; in a low- level language the address in memory of a value is needed instead of its position in the array, so we replace the line col = xion[ym][xm] with the line col = [ xion + 2*rho*ym + xm ] (This assumes that one byte is used for each of the values in the Complexion.) 5.5.1. The use of xm and ym to point to values in the Complexion is somewhat inefficient. One fairly simple way of speeding the process up would be to store the value of 2*rho*ym or even xion+2*rho*ym in the Gush instead of just ym. The modulus ('%') calculation can also be made faster by choosing a value for rho that is a power of two; then the modulus operation can be replaced by a logical AND operation which most microprocessors can perform much faster. If this is done then the central loop of the routine will look something like: xm = [gush++] ym2 = [gush++] xm = ( xm + rot ) AND (2*rho-1) col = [ ym2 + xm ] [scr] = col scr += 1 5.5.2. An alternative approach can be used on CPUs which allow their 16- or 32-bit registers to be split into component 8-bit registers. Suppose one complete register is called yyxx and that its lowest 8 bits can be operated upon separately as the register xx. Since xx is only 8 bits long, the equivalent of an AND 255 operation is automatically performed on it whenever it is used. Thus if rho is set equal to 128 and the Gush holds the combined value 2*rho*ym+xm instead of both xm and ym, then the core of the routine is simply: yyxx = [gush++] xx += rot col = [ xion + yyxx ] [scr] = col scr += 1 5.5.3. There is yet a third way to simplify the routine, though it requires twice as much memory for the Complexion data. An expanded Complexion is created in which each line of the map appears twice: Line 1 is followed in memory by another copy of Line 1 before getting to Line 2, such that [xion] is the same as [xion+2*rho], [xion+1] is the same as [xion+2*rho+1], and so on up until [xion+4*rho] which is the start of the second line. An expanded Complexion removes the need for the modulus ('%') calculation when rot is added on to xm. Instead of the two values xm and ym being used for each point in the Line Gush, the single combined value xion+4*rho*ym+xm (or possibly just 4*rho*ym+xm) is used. The single variable/register ymxm replaces both xm and ym and the core of the routine now becomes: ymxm = [gush++] col = [ ymxm + rot ] ( or [ xion + ymxm + rot ] ) [scr] = col scr += 1 (Note that 4*rho now replaces 2*rho as the width of the Complexion array.) 5.6. Scattered Jumps There is another aspect of the display routine which can still be made more efficient: the looping mechanism. For every point of the planet that is plotted, additional instructions must be executed to loop back to plot the next point. These time wasting loop instructions can be missed out by repeating the plotting code in memory once for each of the points to be plotted. The problem with this is that the number of points to be plotted on each line varies. The solution is to miss out some of the plot routines by jumping past them - this needs an 'indirect' jump instruction, the address to jump to being stored in a register or in memory. The following code shows how this method could be implemented into a display routine. It is based around an expanded Complexion, as described in the previous sub-section. The value in the Gush which used to be the number of points to plot on this line is now an address to jump to in order to plot that number of points. ycount = [gush++] L1: scr += [gush++] jump to [gush++] [...] * ymxm = [gush++] * col = [ ymxm + rot ] * [scr] = col * scr += 1 ycount -= 1 if ( ycount != 0 ) jump to L1 The code marked by the asterisks plots one point. Assuming that MAX_R is the largest value of RADIUS ever likely to be used in the program, then the asterisked code needs to be repeated 2*MAX_R times. The complete routine should take up no more than a few kilobytes. 5.7. The Compiled Gush This is a way by which the animation can be dramatically increased in speed (and thanks to Jamie Lokier for pointing this out): instead of the Gush containing numerical data to be read by an animation routine, it can itself be an executable routine with the data hard-wired into it. The Square Gush is translated directly into machine code, with a few bytes of code for each of the points to be plotted. A section of the Compiled Gush (working with an expanded Complexion) would then look something like: col = [ m1 + rot ] [scr] = col scr += 1 col = [ m2 + rot ] [scr] = col scr += 1 col = [ m3 + rot ] [scr] = col scr += 1 [...] where m1, m2 and m3 are immediate (constant) values. The Compiled Gush also contains machine instructions to move scr from the end of one line to the start of the next, and, of course, a 'return' instruction at the end. (Furthermore, quite a bit of optimization can often be done on the code as it is generated.) The planet is then animated simply by choosing values for scr and rot and calling the Compiled Gush code. But there is one big drawback to this: a Compiled Gush takes up a lot of memory, several times more than a normal Gush. Fast animation is what this method delivers, but it does so at the cost of a large chunk of memory. 6. Finishing Off 6.1. Putting Together the Pieces Way back at the beginning of all this I described the animation program as consisting of three basic parts. The code for creating Gush data is detailed in Section 2, the code for creating Complexion data is detailed in Section 3, and Section 5 constructs a routine that draws a planet using these two data arrays. In Section 1.4, constant values (rho, RADIUS, DIST, etc.) are introduced. Whatever values these constants are given it is important that they remain the same in all parts of the program. With all segments of the program complete an animation can finally be put together. The simplest animation, that of a planet spinning in the centre of the screen, is accomplished in the following way. Create a Gush and a Complexion, storing both in files on disk. Write a simple piece of code that first loads in both data files and then, with an appropriate value for scr (the point on the screen where the planet is to appear), repeatedly calls the display routine. The additional parameter rot is increased (or decreased) by a small, fixed amount on each call with a modulus operation keeping it in the range 0 to 2*rho-1. There is not much more to say about the animation; further elaborations are left to the programmer's imagination. As a few suggestions: * Store several different Gushes on disk and select one to use at random when the animation is run. The Gushes are all created using different values for phi and theta (and possibly RADIUS). * Use different sets of colours for different planets; choose the set to be used at random when converting a Skin to a Complexion. * Make more interesting planet surfaces; add random cloud and mountain generation, or edit a Complexion using a standard bitmap editor to give it a smiling face. * Draw a star field behind the planet (to make the fact that it's supposed to be a planet more obvious!). Animate the star field. * Shade the planet (as described in the next sub-section). * Before displaying the next frame of the planet, delete the old frame and change the value of scr so that the planet appears in a different place. Make the planet move. Make it bounce! 6.2. Illumination In Section 2.3, when calculating values for the Gush a vector P=(xp,yp,zp) is generated for each point (xs,ys). This vector can be used to give a basic illumination effect, that of light shining onto the planet from a fixed direction. For this effect to work, some method for selectively altering the brightness of the pixels making up the planet's image is needed. Ideally, each pixel should have a collection of bits controlling its brightness which are independent of the bits controlling its colour. The planet can then be shaded by adjusting just these brightness bits. Define a vector I=(xi,yi,zi) as the direction from which light falls onto the planet. Then, for each (xs,ys), calculate a value lambda as follows: q = sqrt( xi*xi + yi*yi + zi*zi ) lambda = ( I . P ) / ( |I| * |P| ) = ( xi*xp + yi*yp + zi*zp ) / ( q * g ) (The calculation of the constant g is described in Section 2.3) lambda is a measure of the illumination of the point (xs,ys) and takes values from -1 (minimum brightness) to +1 (maximum brightness). (Strictly, if lambda's value is below zero, then no light at all reaches (xs,ys) - it is on the dark side of the planet.) Transform each lambda into a number kappa, the value to be put in the brightness bits of the pixel at (xs,ys). To avoid the shading of the planet being too regular, add a slight random influence to the transformation such as changing the value of lambda by a small, random amount. This blurs the border between 'light' and 'dark' regions of the planet. Illuminating the planet is now a matter of keeping the brightness of each pixel fixed (at the value kappa) whilst allowing the planet display routine to fill in the pixel's colour. One way of doing this would be to set each pixel to brightness kappa and colour zero, and then use a logical OR operation in the display routine to overlay colours onto the pixels. Before drawing the next frame, the colour of each pixel would need to be reset to zero, either by rewriting all brightness and colour values together, or by resetting just the colour bits using multiple logical AND operations. 6.3. Whys and Wherefores That's about it really. The one thing left to add is an explanation. I've written some seven thousand words describing how to put together a pretty but pointless animation. Why did I bother? Well, as I said earlier, nearly all of the mildly clever animation techniques used here I've had to work out for myself. They aren't the sort of thing that you commonly find in text books. In a way this document is a small attempt to change that - it's sort of a "Beginner's Guide to Real-time Animation (Volume 1: Things That Bounce)". Also, there's a limit to the number of things that I can think of to do to spinning planets. I want to see what ideas other people come up with using this as a starting point. So, having read this document, if you're interested in bringing this animation to life, go to it, and good luck to you. 6.4. Acknowledgements Thanks must go to Matt Spinner for helping create the original planet demo and to everyone else who was around at the time (Dave, Nick, Simon, Phill, JT, etc). And thanks also to Jay Dresser and Jamie Lokier from Usenet for comments on the original posting.